#include "utils.h"
#include "leetcode.h"

int *twoSum(int *nums, int numsSize, int target, int *returnSize)
{
    int *result = (int *)malloc(sizeof(int) * 2);
    for (int i = 0; i < numsSize; i++)
    {
        for (int j = i + 1; j < numsSize; j++)
        {
            if (nums[i] + nums[j] == target)
            {
                *returnSize = 2;
                result[0] = i;
                result[1] = j;
                return result;
            }
        }
    }
    *returnSize = 0;
    return result;
}

bool isPalindrome(int x)
{
    // 如果 x 小于 0，直接返回 false
    if (x < 0)
    {
        return false;
    }

    int original = x;
    long reversed = 0;

    // 反转整数
    while (x > 0)
    {
        reversed = reversed * 10 + x % 10;
        x /= 10;
    }

    // 判断反转后的整数是否与原始整数相等
    return (original == reversed);
}

char *longestCommonPrefix(char **strs, int strsSize)
{
    // char *s0 = strs[0];
    // strdup 是一个标准C库函数，用于动态分配内存并复制字符串。它的全称是 "string duplicate"。strdup 函数在 string.h 头文件中声明。

    char *s0 = strdup(strs[0]);
    for (int j = 0; s0[j]; j++)
    {
        for (int i = 0; i < strsSize; i++)
        {
            if (strs[i][j] != s0[j])
            {
                s0[j] = '\0';
                return s0;
            }
        }
    }
    return s0;
}

bool isValid(char *s)
{

    // 使用栈来解决这个问题。栈是后进先出（LIFO）的数据结构，特别适合处理括号匹配的问题。
    int len = strlen(s);
    if (len == 0)
        return true;

    // 栈
    char stack[len];
    int top = -1;

    // 遍历字符串
    for (int i = 0; i < len; i++)
    {
        char ch = s[i];

        if (ch == '(' || ch == '{' || ch == '[')
        {
            // 左括号入栈
            stack[++top] = ch;
        }
        else
        {
            // 右括号匹配
            if (top == -1)
                return false;
            char topCh = stack[top--];

            if ((ch == ')' && topCh != '(') ||
                (ch == '}' && topCh != '{') ||
                (ch == ']' && topCh != '['))
            {
                return false;
            }
        }
    }

    // 栈为空说明括号完全匹配
    return top == -1;
}

struct ListNode *mergeTwoLists(struct ListNode *list1, struct ListNode *list2)
{
    // 创建一个哑节点（dummy node），并初始化一个指针current指向它
    struct ListNode dummy;
    struct ListNode *current = &dummy;
    dummy.next = NULL;

    // 遍历两个链表，直到其中一个链表为空
    while (list1 != NULL && list2 != NULL)
    {
        // 比较两个链表的当前节点的值，选择较小的节点连接到current节点后面
        if (list1->val <= list2->val)
        {
            current->next = list1;
            list1 = list1->next;
        }
        else
        {
            current->next = list2;
            list2 = list2->next;
        }
        current = current->next; // 移动current指针到新的尾节点
    }

    // 如果list1还有剩余节点，则直接连接到current后面
    if (list1 != NULL)
    {
        current->next = list1;
    }
    // 如果list2还有剩余节点，则直接连接到current后面
    if (list2 != NULL)
    {
        current->next = list2;
    }

    // 返回合并后的链表，跳过哑节点
    return dummy.next;
}

int removeDuplicates(int *nums, int numsSize)
{
    if (numsSize == 0)
        return 0;

    int j = 1; // 下一个非重复元素的位置
    for (int i = 1; i < numsSize; i++)
    {
        if (nums[i] != nums[i - 1])
        {
            nums[j] = nums[i];
            j++;
        }
    }
    return j;
}

int removeElement(int *nums, int numsSize, int val)
{
    int j = 0; // 下一个保留元素的位置
    for (int i = 0; i < numsSize; i++)
    {
        if (nums[i] != val)
        {
            nums[j] = nums[i];
            j++;
        }
    }
    return j;
}

int strStr(char *haystack, char *needle)
{
    int haystackLen = strlen(haystack);
    int needleLen = strlen(needle);

    for (int i = 0; i <= haystackLen - needleLen; i++)
    {
        int j = 0;
        for (; j < needleLen; j++)
        {
            if (haystack[i + j] != needle[j])
            {
                break;
            }
        }
        if (j == needleLen)
        {
            return i;
        }
    }
    return -1;
}

int searchInsert(int *nums, int numsSize, int target)
{
    int i = 0;
    for (; i < numsSize; i++)
    {
        if (nums[i] == target)
        {
            return i;
        }
        if (nums[i] > target)
        {
            return i;
        }
    }

    return numsSize;
}

int lengthOfLastWord(char *s)
{

    int length = 0;
    int i = strlen(s) - 1;

    // Skip trailing spaces
    while (i >= 0 && s[i] == ' ')
    {
        i--;
    }

    // Calculate the length of the last word
    while (i >= 0 && s[i] != ' ')
    {
        length++;
        i--;
    }

    return length;
}

int *plusOne(int *digits, int digitsSize, int *returnSize)
{

    int carry = 1; // Initialize carry as 1, since we are adding 1
    for (int i = digitsSize - 1; i >= 0; i--)
    {
        int sum = digits[i] + carry;
        digits[i] = sum % 10;
        carry = sum / 10;
    }

    if (carry == 0)
    {
        // No carry, the size of the result is the same as the input
        *returnSize = digitsSize;
        return digits;
    }
    else
    {
        // There is a carry, the size of the result is digitsSize + 1
        *returnSize = digitsSize + 1;
        int *result = (int *)malloc(*returnSize * sizeof(int));
        result[0] = 1; // The carry becomes the new leading digit
        for (int i = 1; i < *returnSize; i++)
        {
            result[i] = digits[i - 1];
        }
        return result;
    }
}

char *addBinary(char *a, char *b)
{
    int lenA = strlen(a);
    int lenB = strlen(b);
    int maxLength = lenA > lenB ? lenA : lenB;

    // Allocate memory for the result. +2 to account for possible carry and null terminator
    char *result = (char *)malloc(maxLength + 2);
    result[maxLength + 1] = '\0';

    int carry = 0;
    int i = lenA - 1, j = lenB - 1, k = maxLength;

    while (i >= 0 || j >= 0 || carry)
    {
        int sum = carry;
        if (i >= 0)
            sum += a[i--] - '0';
        if (j >= 0)
            sum += b[j--] - '0';

        result[k--] = (sum % 2) + '0';
        carry = sum / 2;
    }

    // If there is no carry, move the result to the beginning of the buffer
    if (k == 0)
    {
        memmove(result, result + 1, maxLength + 1);
    }

    return result;
}

int mySqrt(int x)
{
    // 牛顿迭代法
    if (x == 0)
        return 0;

    double y = x;
    double epsilon = 1e-6; // 设定精度

    while ((y * y - x) > epsilon)
    {
        y = (y + x / y) / 2.0;
    }

    return (int)y;
}

int climbStairs(int n)
{
    if (n <= 1)
        return 1;

    // 动态数组，用于存储到达每一阶楼梯的方法数
    int *dp = (int *)malloc((n + 1) * sizeof(int));

    // 初始化
    dp[0] = 1;
    dp[1] = 1;

    // 填充dp数组
    for (int i = 2; i <= n; i++)
    {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    int result = dp[n];

    free(dp); // 释放动态分配的内存

    return result;
}

struct ListNode *deleteDuplicates(struct ListNode *head)
{
    if (head == NULL)
        return NULL;

    struct ListNode *current = head;
    while (current != NULL && current->next != NULL)
    {
        if (current->val == current->next->val)
        {
            // 删除重复节点
            struct ListNode *temp = current->next;
            current->next = current->next->next;
            free(temp); // 释放内存
        }
        else
        {
            current = current->next;
        }
    }

    return head;
}

void merge(int *nums1, int nums1Size, int m, int *nums2, int nums2Size, int n)
{
    int i = m - 1;
    int j = n - 1;
    int k = m + n - 1;

    while (i >= 0 && j >= 0)
    {
        if (nums1[i] > nums2[j])
        {
            nums1[k] = nums1[i];
            i--;
        }
        else
        {
            nums1[k] = nums2[j];
            j--;
        }
        k--;
    }

    while (j >= 0)
    {
        nums1[k] = nums2[j];
        j--;
        k--;
    }
}

// 辅助函数：递归遍历二叉树的中序遍历，并将结果存储在数组中
void inorder(struct TreeNode *root, int *result, int *returnSize)
{
    if (root == NULL)
    {
        return;
    }

    // 遍历左子树
    inorder(root->left, result, returnSize);

    // 处理当前节点
    result[(*returnSize)++] = root->val;

    // 遍历右子树
    inorder(root->right, result, returnSize);
}

int *inorderTraversal(struct TreeNode *root, int *returnSize)
{
    *returnSize = 0;
    int capacity = 100; // 初始容量，可以根据需要调整
    int *result = (int *)malloc(sizeof(int) * capacity);

    if (result == NULL)
    {
        // 内存分配失败，返回空
        return NULL;
    }

    // 辅助函数进行中序遍历
    inorder(root, result, returnSize);

    return result;
}

bool isSameTree(struct TreeNode *p, struct TreeNode *q)
{

    if (p == NULL && q == NULL)
    {
        return true;
    }
    if (p == NULL || q == NULL)
    {
        return false;
    }
    if (p->val != q->val)
    {
        return false;
    }
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

// 辅助函数，用于检查两棵子树是否是镜像
bool isMirror(struct TreeNode *left, struct TreeNode *right)
{
    if (left == NULL && right == NULL)
    {
        return true;
    }
    if (left == NULL || right == NULL)
    {
        return false;
    }
    if (left->val != right->val)
    {
        return false;
    }
    return isMirror(left->left, right->right) && isMirror(left->right, right->left);
}

bool isSymmetric(struct TreeNode *root)
{
    if (root == NULL)
    {
        return true;
    }
    return isMirror(root->left, root->right);
}

int maxDepth(struct TreeNode *root)
{
    if (root == NULL)
    {
        return 0;
    }
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}

// 辅助函数：创建一个新的二叉树节点
struct TreeNode *newNode(int val)
{
    struct TreeNode *node = (struct TreeNode *)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 辅助函数：将有序数组转换为BST
struct TreeNode *sortedArrayToBSTHelper(int *nums, int left, int right)
{
    if (left > right)
    {
        return NULL;
    }

    // 选择中间元素作为根节点
    int mid = left + (right - left) / 2;
    struct TreeNode *root = newNode(nums[mid]);

    // 递归地构造左子树和右子树
    root->left = sortedArrayToBSTHelper(nums, left, mid - 1);
    root->right = sortedArrayToBSTHelper(nums, mid + 1, right);

    return root;
}

struct TreeNode *sortedArrayToBST(int *nums, int numsSize)
{
    if (numsSize == 0)
    {
        return NULL;
    }
    return sortedArrayToBSTHelper(nums, 0, numsSize - 1);
}

// 辅助函数：计算二叉树的高度
int height(struct TreeNode *root)
{
    if (root == NULL)
    {
        return 0;
    }
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);
    if (leftHeight == -1 || rightHeight == -1 || abs(leftHeight - rightHeight) > 1)
    {
        return -1; // 用于标记不平衡
    }
    return fmax(leftHeight, rightHeight) + 1;
}

bool isBalanced(struct TreeNode *root)
{
    return height(root) != -1;
}

int minDepth(struct TreeNode *root)
{
    if (root == NULL)
    {
        return 0;
    }

    // 如果左子树为空，递归计算右子树的最小深度
    if (root->left == NULL)
    {
        return minDepth(root->right) + 1;
    }

    // 如果右子树为空，递归计算左子树的最小深度
    if (root->right == NULL)
    {
        return minDepth(root->left) + 1;
    }

    // 如果左右子树都不为空，返回左右子树的最小深度加1
    int leftDepth = minDepth(root->left);
    int rightDepth = minDepth(root->right);
    return (leftDepth < rightDepth ? leftDepth : rightDepth) + 1;
}

bool hasPathSum(struct TreeNode *root, int targetSum)
{
    // 如果根节点为空，直接返回 false
    if (root == NULL)
    {
        return false;
    }

    // 如果当前节点是叶子节点（左右子节点都为空），判断当前节点值是否等于 targetSum
    if (root->left == NULL && root->right == NULL)
    {
        return targetSum == root->val;
    }

    // 递归判断左子树或右子树中是否存在满足条件的路径
    return hasPathSum(root->left, targetSum - root->val) || hasPathSum(root->right, targetSum - root->val);
}

int **generate(int numRows, int *returnSize, int **returnColumnSizes)
{
    // *returnSize 保存行数 numRows。
    // *returnColumnSizes 分配一个数组来保存每行的列数（即行的长度）。
    // triangle 分配一个二维数组表示杨辉三角。

    // 分配返回大小
    *returnSize = numRows;

    // 分配列大小数组
    *returnColumnSizes = (int *)malloc(numRows * sizeof(int));
    int **triangle = (int **)malloc(numRows * sizeof(int *));

    for (int i = 0; i < numRows; i++)
    {
        (*returnColumnSizes)[i] = i + 1; // 每行的列数
        triangle[i] = (int *)malloc((i + 1) * sizeof(int));
        triangle[i][0] = 1; // 每行的第一个元素为1
        triangle[i][i] = 1; // 每行的最后一个元素为1

        // 中间元素
        for (int j = 1; j < i; j++)
        {
            triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
        }
    }

    return triangle;
}

void printTriangle(int **triangle, int numRows, int *columnSizes)
{
    for (int i = 0; i < numRows; i++)
    {
        for (int j = 0; j < columnSizes[i]; j++)
        {
            printf("%d ", triangle[i][j]);
        }
        printf("\n");
    }
}

int *getRow(int rowIndex, int *returnSize)
{

    // 分配返回大小
    *returnSize = rowIndex + 1;

    // 分配列大小数组
    int *returnColumnSizes = (int *)malloc(*returnSize * sizeof(int));
    int **triangle = (int **)malloc(*returnSize * sizeof(int *));

    for (int i = 0; i < *returnSize; i++)
    {
        (returnColumnSizes)[i] = i + 1; // 每行的列数
        triangle[i] = (int *)malloc((i + 1) * sizeof(int));
        triangle[i][0] = 1; // 每行的第一个元素为1
        triangle[i][i] = 1; // 每行的最后一个元素为1

        // 中间元素
        for (int j = 1; j < i; j++)
        {
            triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
        }
    }
    // printTriangle(triangle, *returnSize, returnColumnSizes);
    return triangle[rowIndex];
}

bool isPalindrome(char *s)
{
    int len = strlen(s);
    // 动态分配内存来保存处理后的字符串
    char *filtered = (char *)malloc(len + 1);
    int index = 0;

    // 过滤非字母数字字符，并将字母转换为小写
    for (int i = 0; i < len; i++)
    {
        if (isalnum(s[i]))
        {
            filtered[index++] = tolower(s[i]);
        }
    }
    filtered[index] = '\0'; // 结束字符串

    // 判断处理后的字符串是否是回文
    int start = 0;
    int end = index - 1;
    while (start < end)
    {
        if (filtered[start] != filtered[end])
        {
            free(filtered); // 释放分配的内存
            return false;
        }
        start++;
        end--;
    }

    free(filtered); // 释放分配的内存
    return true;
}

int singleNumber(int *nums, int numsSize)
{
    // 异或运算满足交换律和结合律，而且任何数和自己异或的结果是 0，任何数和 0 异或的结果是它本身。
    //  任何数和 0 异或的结果是它本身，即 a ^ 0 = a。
    // 任何数和自己异或的结果是 0，即 a ^ a = 0。
    // 异或运算满足交换律和结合律，即 a ^ b ^ a = b。
    int result = 0;
    for (int i = 0; i < numsSize; i++)
    {
        result ^= nums[i];
    }
    return result;
}

bool hasCycle(struct ListNode *head)
{
    if (head == NULL || head->next == NULL)
    {
        return false;
    }

    struct ListNode *slow = head;
    struct ListNode *fast = head->next;

    while (slow != fast)
    {
        if (fast == NULL || fast->next == NULL)
        {
            return false;
        }
        slow = slow->next;
        fast = fast->next->next;
    }

    return true;
}

void preorder(struct TreeNode *root, int *result, int *returnSize)
{
    if (root == NULL)
    {
        return;
    }
    // 处理当前节点
    result[(*returnSize)++] = root->val;
    // 遍历左子树
    preorder(root->left, result, returnSize);

    // 遍历右子树
    preorder(root->right, result, returnSize);
}
int *preorderTraversal(struct TreeNode *root, int *returnSize)
{
    *returnSize = 0;
    int capacity = 100; // 初始容量，可以根据需要调整
    int *result = (int *)malloc(sizeof(int) * capacity);
    preorder(root, result, returnSize);
    return result;
}